1. Field of the Invention
This invention relates to multipass numerical sorting and more particularly to sorting where the input list is divided into sorted groups which are identically stored within concurrently accessed twin interstage buffers.
2. Description of the Prior Art
Heretofore, numerical sorting was done primarily by relatively slow software programs. The limited sorting hardware that was available is based on a cumbersome comparison technique which sometimes required more comparator elements than words in the input list. In some instances the circuitry required increased geometrically as the number N of elements in the input list expanded. Further, these prior art hardware and software sorters are not fast enough for CRT display applications. U.S. patent application Ser. No. 622,911 teaches multipass hardware sorting with minimum circuit requirements. FIGS. 1-7 of this specification, and the detailed description associated therewith, were taken from the above U.S. patent application. In Ser. No. 622,911 the input numbers were arranged into S2 groups of S1 numbers each. The numbers within each S2 groups were arranged in numerical order by a first sorting stack having S1 locations. The smallest number in each group was then entered into a second sorting stack having S2 locations and arranged into numerical order. As the first number in the second stack (the smallest number in the input list) was clocked out, a replacement number was accessed from one of the groups and clocked into the second stack and numerically sorted. The replacement number in Ser. No. 622,911 was always the next number from the same group as the number just clocked out. In the present invention this access time is eliminated by accessing two candidates for the next replacement number simultaneously as the currently clocked out number is replaced by the current replacement number. When the next replacement number becomes the current replacement number, no accessing is required; the two candidates are merely compared and the smallest one is clocked into the second stage as the current replacement number. Accessing next replacement numbers in advance shortens the clock period for clocking out the smallest remaining number in the second stack.